A lookup is a data search performed within a predefined table of values. Lookups are performed frequently in the process of handling network traffic. For example, lookups may be performed in relation to a traffic distribution policy table or an access control list (ACL). In a lookup, information from incoming packets, such as header information, is used to compare against information stored in a lookup table to determine how the packet should be handled. In the process of handling network traffic, multiple lookups may be performed using information from different protocol layers, such as layer three (3) and layer four (4), where the layers are defined by the International Standards Organization (ISO) in the Open System Interconnection (OSI) model. As defined in the OSI model, layer 3 (L3) (also referred to as the network layer) is used to route data to different local area networks (LANs) and wide area networks (WANs) based on network address (i.e., destination IP address). Layer 4 (L4) (also referred to as the transport layer) can be used to ensure delivery of an entire file or message. L3 lookups are commonly performed in order to determine a next hop for the packet. L4 lookups are commonly performed to implement a traffic distribution policy or for access control. Typically, L3 lookups and L4 lookups are performed in parallel. FIG. 1 is a logical depiction of conventional L3 and L4 lookup processes that are performed in parallel on incoming traffic. The two lookups are performed independently of each other using header information that is obtained from the incoming traffic.
FIG. 2 is an example of a lookup table (referred to as an “L3 lookup table”) that is used to forward Internet Protocol (IP) traffic to the next hop. In the embodiment of FIG. 2, the search field of the lookup table includes a “Source IP Address” and a “Dest. IP Address” (destination IP address). And the results field of the lookup table includes some associated data. For example, the associated data may include next hop information and/or a pointer to another location that holds next hop information. In the embodiment of FIG. 2, the source IP address is irrelevant (as indicated by the “X” values) because incoming packets are matched solely based upon destination IP addresses.
FIG. 3 is an example of a lookup table (referred to as an “L4 lookup table”) that is used to implement, for example, a traffic distribution policy or access control. In the embodiment of FIG. 3, the search field of the lookup table includes “Source IP Address,” “Dest. IP Address” (destination IP address), “Source Socket,” “Dest. Socket” (destination socket). And the results field of the lookup table includes some associated data. For example, the associated data may include next hop information for application of a traffic distribution policy or a “permit/deny” determination for access control. As stated above with reference to FIG. 1, the L4 lookup is performed in parallel with the L3 lookup. Note that the source IP address in the L4 lookup is irrelevant, in this case, because incoming packets are matched based upon destination IP address, source socket, and destination socket. Since the L4 lookup is performed in parallel with the L3 lookup, information obtained from the L3 lookup cannot be used to benefit the L4 lookup. In addition, the L4 lookup table is populated with one L4 table entry for each combination of destination IP address, source socket, and destination socket.
Some packets have particular commonalities with other packets based on L4 information. For example, multiple entries may identify the same source and destination sockets and the same associated data even though their destination IP addresses differ. For example, the first, fourth, seventh, and tenth L4 table entries (destination IP address 10.1.1.1, source socket A, destination socket B), (destination IP address 11.1.1.1, source socket A, destination socket B), (destination IP address 12.1.1.1, source socket A, destination socket B), and (destination IP address 13.1.1.1, source socket A, destination socket B) all yield the same associated data (traffic info “H”). That is, packets having these characteristics are all handled in a similar manner.
Lookup tables are often implemented in network nodes using memory such as random access memory (RAM) and/or content addressable memory (CAM). In order to implement larger lookup tables, more memory is needed. Memory in a network node is a costly resource that should be used efficiently.
Because memory is a costly resource, what is needed is an efficient technique for implementing multiple lookups in a network node.